class Solution {
public:

    //n个点可以构成n-2个三角形
    const int INF=0x3f3f3f3f;
    unordered_map<int, int> memo; //记忆化搜索

    int dp(vector<int> &values, int n, int i, int j) //i到j这个多边形在三角剖分后得到的最低得分
    {   
        if(i+1==j) return 0; //只有两个点，不构成三角形 (i, j)为空区间
        if(i+2==j) return values[i]*values[i+1]*values[j];

        int key=i*n+j;
        if(!memo.count(key))
        {
            int minScore=INF;
            for(int k=i+1; k<j; k++) //枚举(i, j)中的中间节点，得到i->j的最小值
                minScore=min(minScore, values[i]*values[k]*values[j]+dp(values, n, i, k)+dp(values, n, k, j));
            memo[key]=minScore;
        }
        return memo[key];
    }

    int minScoreTriangulation(vector<int>& values) {
        int n=values.size();
        vector<vector<int>> f(n, vector<int>(n, 0));
        for(int i=n-3; i>=0; i--)
        {
            for(int j=i+2; j<n; j++)
            {
                f[i][j]=INF;
                for(int k=i+1; k<j; k++)
                    f[i][j]=min(f[i][j], f[i][k]+f[k][j]+values[i]*values[j]*values[k]);
            }
        }
        // return dp(values, n, 0, n-1);
        return f[0][n-1];
    }
};